An object-relational database system may be implemented on top of object storage servers. A database schema defines a set of tables, indexes, columns and locks that form a database. The columns can have complex types or structures, such as a “struct” in C++ or a “class” in Java. In accordance with the schema, database servers may handle requests from user devices. Examples of such requests may be to add or drop values from a column or row. The schema may instruct the database server as to how to handle the request. For example, if the request is to add a row, the schema may instruct the database server to correspondingly update the index.
When a change from a first database schema to a second database schema is desired, problems may be encountered for various reasons. For example, the database servers cannot delay requests from user devices due to a schema change, nor can they fail requests due to a schema change. Moreover, the database servers may be distributed across several datacenters, and may not have knowledge of each other. Consequently, the new schema cannot be applied synchronously to all servers, and therefore at a given time, some database servers will use the old schema and other will use the new schemas to read or write the same data. This may result in concurrency anomalies that corrupt the database. For example, a server using the new schema inserts a row. The new schema contains a new index, so the server also inserts a corresponding index entry. Subsequently, another server using the old schema deletes the row. The schema does not contain the new index, and hence the server does not delete the index entry and thereby corrupts the database.